#pragma once

#ifndef __SALTBUFFERARRAY
#define __SALTBUFFERARRAY


#include "SaltHandle.h"							// CSaltHandle<>




	#define SALT_DEFAULT_SIZE (64*1024)


// use one instance of this class in your object manager
// quite efficient implementation, avoids use of pointer to save memory and reduce cache misses
template <class TSalt = unsigned short, class TIndex = unsigned short, unsigned int Size = SALT_DEFAULT_SIZE - 3>
class CSaltBufferArray
{
	enum ESpecialIndexValue
	{
		eSIV_EndOfFreeList = -1,
		eSIV_NotInFreeList = -2,
	};

public:
	// constructor
	CSaltBufferArray()
	{
		assert((TIndex)Size != (TIndex)eSIV_EndOfFreeList);
		assert((TIndex)Size != (TIndex)eSIV_NotInFreeList);

		Reset();
	}

	// reset (don't use old handles after calling reset)
	void Reset()
	{
		m_maxUsed = Size - 1;

		// back to front
		TIndex i;
		for (i = m_maxUsed; i > 1; --i)
		{
			m_Buffer[i].m_Salt = 0;
			m_Buffer[i].m_NextIndex = i - 1;
		}
		assert(i == 1);

		m_Buffer[1].m_Salt = 0;
		m_Buffer[1].m_NextIndex = (TIndex)eSIV_EndOfFreeList;

		m_FreeListStartIndex = Size - 1;

		// 0 is not used because it's nil
		m_Buffer[0].m_Salt = ~0;
		m_Buffer[0].m_NextIndex = (TIndex)eSIV_NotInFreeList;
	}

	// max index that is allowed for TIndex (max entity count at a time)
	static TIndex GetTSize()
	{
		return Size;
	}

	// O(n) n=FreeList Size
	// useful for serialization (Reset should be called before inserting the first known element)
	// Arguments:
	//   Handle - must be not nil
	void InsertKnownHandle(const CSaltHandle<TSalt, TIndex> handle)
	{
		assert((bool)handle);		// must be not nil

		if (!IsUsed(handle.GetIndex()))
		{
			RemoveFromFreeList(handle.GetIndex());
		}

		if (handle.GetIndex() > m_maxUsed)
		{
			m_maxUsed = handle.GetIndex();
		}

		SSaltBufferElement& rElement = m_Buffer[handle.GetIndex()];
		
		rElement.m_Salt = handle.GetSalt();
		rElement.m_NextIndex = (TIndex)eSIV_NotInFreeList;
	}

	// O(1) = fast
	// Returns:
	//   nil if there was not enough space, valid SaltHandle otherwise
	CSaltHandle<TSalt, TIndex> InsertDynamic()
	{
		if (m_FreeListStartIndex == (TIndex)eSIV_EndOfFreeList)
			return CSaltHandle<TSalt,TIndex>();		// buffer is full

		// update bounds
		if (m_FreeListStartIndex > m_maxUsed)
		{
			m_maxUsed = m_FreeListStartIndex;
		}

		CSaltHandle<TSalt, TIndex> ret(m_Buffer[m_FreeListStartIndex].m_Salt, m_FreeListStartIndex);

		SSaltBufferElement& rElement = m_Buffer[m_FreeListStartIndex];

		m_FreeListStartIndex = rElement.m_NextIndex;
		rElement.m_NextIndex = (TIndex)eSIV_NotInFreeList;

		assert(IsUsed(ret.GetIndex()));		// Index was not used, Insert() wasn't called or Remove() called twice

		return ret;
	}

	// O(n) = slow
	// Returns:
	//   nil if there was not enough space, valid SaltHandle otherwise
	CSaltHandle<TSalt, TIndex> InsertStatic()
	{
		if (m_FreeListStartIndex == (TIndex)eSIV_EndOfFreeList)
			return CSaltHandle<TSalt, TIndex>();		// buffer is full

		// find last available index O(n)
		TIndex LastFreeIndex = m_FreeListStartIndex;
		TIndex* pPrevIndex = &m_FreeListStartIndex;

		for (;;)
		{
			SSaltBufferElement& rCurrElement = m_Buffer[LastFreeIndex];

			if (rCurrElement.m_NextIndex == (TIndex)eSIV_EndOfFreeList)
				break;

			pPrevIndex = &(rCurrElement.m_NextIndex);
			LastFreeIndex = rCurrElement.m_NextIndex;
		}

		// remove from end
		*pPrevIndex = (TIndex)eSIV_EndOfFreeList;

		// update bounds (actually with introduction of InsertStatic/Dynamic() the m_maxUsed becomes useless)
		if (LastFreeIndex > m_maxUsed)
		{
			m_maxUsed = LastFreeIndex;
		}

		CSaltHandle<TSalt, TIndex> ret(m_Buffer[LastFreeIndex].m_Salt, LastFreeIndex);

		SSaltBufferElement& rElement = m_Buffer[LastFreeIndex];

		rElement.m_NextIndex = (TIndex)eSIV_NotInFreeList;	// mark used

		assert(IsUsed(ret.GetIndex()));		// Index was not used, Insert() wasn't called or Remove() called twice

		return ret;
	}

	// O(1) - don't call for invalid handles and don't remove objects twice
	void Remove(const CSaltHandle<TSalt, TIndex> handle)
	{
		assert((bool)handle);			// must be not nil

		TIndex index = handle.GetIndex();

		assert(IsUsed(index));		// Index was not used, Insert() wasn't called or Remove() called twice

		TSalt& rSalt = m_Buffer[index].m_Salt;
		TSalt oldSalt = rSalt;

		assert(handle.GetSalt() == oldSalt);

		rSalt++;

		assert(rSalt > oldSalt);		// if this fails a wraparound occurred (thats severe) todo: check in non debug as well
		(void)oldSalt;

		m_Buffer[index].m_NextIndex = m_FreeListStartIndex;
		m_FreeListStartIndex = index;
	}

	// for pure debugging purpose
	void Debug()
	{
		if (m_FreeListStartIndex == (TIndex)eSIV_EndOfFreeList)
		{
			printf("Debug (max size:%d, no free element): ", Size);
		}
		else
		{
			printf("Debug (max size:%d, free index: %d): ", Size, m_FreeListStartIndex);
		}

		for (TIndex i = 0; i < Size; ++i)
		{
			if (m_Buffer[i].m_NextIndex == (TIndex)eSIV_EndOfFreeList)
			{
				printf("%d.%d ", (int)i, (int)m_Buffer[i].m_Salt);
			}
			else
			{
				if (m_Buffer[i].m_NextIndex == (TIndex)eSIV_NotInFreeList)
				{
					printf("%d.%d* ", (int)i, (int)m_Buffer[i].m_Salt);
				}
				else
				{
					printf("%d.%d->%d ", (int)i, (int)m_Buffer[i].m_Salt, (int)m_Buffer[i].m_NextIndex);
				}
			}
		}

		printf("\n");
	}

	// O(1)
	// Returns:
	//   true = handle is referencing to a valid object, false = handle is not or referencing to an object that was removed
	bool IsValid(const CSaltHandle<TSalt, TIndex> handle) const
	{
		if (!handle)
		{
			assert(!"Invalid Handle, please have caller test and avoid call on invalid handle");
			return false;
		}

		if (handle.GetIndex() >= Size)
		{
			assert(0);
			return false;
		}

		return m_Buffer[handle.GetIndex()].m_Salt == handle.GetSalt();
	}

	// O(1) - useful for iterating the used elements, use together with GetMaxUsed()
	bool IsUsed(const TIndex Index) const
	{
		return m_Buffer[Index].m_NextIndex == (TIndex)eSIV_NotInFreeList;			// is marked used?
	}

	// useful for iterating the used elements, use together with IsUsed()
	TIndex GetMaxUsed() const
	{
		return m_maxUsed;
	}

private: // ----------------------------------------------------------------------------------------

	// O(n) n=FreeList Size
	// Returns:
	//   Index must be part of the FreeList
	void RemoveFromFreeList(const TIndex index)
	{
		if (m_FreeListStartIndex == index)	// first index
		{
			m_FreeListStartIndex = m_Buffer[index].m_NextIndex;
		}
		else	// not the first index
		{
			TIndex currentIndex = m_FreeListStartIndex;
			TIndex nextIndex = m_Buffer[currentIndex].m_NextIndex;

			for (;;)
			{
				TIndex nextNextIndex = m_Buffer[nextIndex].m_NextIndex;

				if (nextIndex == index)
				{
					m_Buffer[currentIndex].m_NextIndex = nextNextIndex;
					break;
				}

				assert(nextNextIndex != (TIndex)eSIV_EndOfFreeList);					// end index, would mean the element was not in the list

				currentIndex = nextIndex;
				nextIndex = nextNextIndex;
			}
		}

		m_Buffer[index].m_NextIndex = (TIndex)eSIV_NotInFreeList;
	}

	// ------------------------------------------------------------------------------------------------

	struct SSaltBufferElement
	{
		TSalt m_Salt;					//!< 0.. is counting up on every remove, should never wrap around
		TIndex m_NextIndex;		//!< linked list of free or used elements, (TIndex)eSIV_EndMarker is used as end marker and for not valid elements, eSIV_ValidElement is used for used elements
	};


	SSaltBufferElement	m_Buffer[Size];						//!< freelist and salt buffer elements in one, [0] is not used
	TIndex							m_FreeListStartIndex;			//!< (TIndex)eSIV_EndMarker if empty, index in m_Buffer otherwise
	TIndex							m_maxUsed;								//!< to enable fast iteration through the used elements - is constantly growing execpt when calling Reset()
};


#endif // __SALTBUFFERARRAY
